package tree;

public class BinaryTreeDemo {
	public static void main(String[] args) {
		//需要创建一个二叉树
		BinaryTree binaryTree = new BinaryTree();
		//创建需要的节点
		HeroNode node1 = new HeroNode(1, "qqq");
		HeroNode node2 = new HeroNode(2, "www");
		HeroNode node3 = new HeroNode(3, "eee");
		HeroNode node4 = new HeroNode(4, "rrr");
		HeroNode node5 = new HeroNode(5, "ttt");
		HeroNode node6 = new HeroNode(6, "ttt");

		//为简化操作，手动创建二叉树
		node1.setLeft(node2);
		node1.setRight(node3);
		node2.setLeft(node4);
		node2.setRight(node5);
		node3.setLeft(node6);
		binaryTree.setRoot(node1);

		//测试
		binaryTree.postOrder();
//        binaryTree.deleteNode(9);
//        System.out.println("=========================");
//        binaryTree.preOrder();
	}

}

//定义一个二叉树
class BinaryTree {
	private HeroNode root;

	public void setRoot(HeroNode root) {
		this.root = root;
	}

	//前序遍历(调用 HeroNode 中的方法)
	public void preOrder() {
		if (this.root != null) {
			this.root.preOrder();
		} else {
			System.out.println("为空");
		}
	}

	//前序遍历(调用 HeroNode 中的方法)
	public void infixOrder() {
		if (this.root != null) {
			this.root.infixOrder();
		} else {
			System.out.println("为空");
		}
	}

	//前序遍历(调用 HeroNode 中的方法)
	public void postOrder() {
		if (this.root != null) {
			this.root.postOrder();
		} else {
			System.out.println("为空");
		}
	}

	//前序查找
	public void preOrderSearch(int no) {
		if (root != null) {
			System.out.println(root.preOrderSearch(no));
		} else {
			System.out.println("不存在");
		}
	}

	//中序查找
	public void infixOrderSearch(int no) {
		if (root != null) {
			System.out.println(root.infixOrderSearch(no));
		} else {
			System.out.println("不存在");
		}
	}

	//后序查找
	public void postOrderSearch(int no) {
		if (root != null) {
			System.out.println(root.postOrderSearch(no));
		} else {
			System.out.println("不存在");
		}
	}

	//删除节点
	public void deleteNode(int no) {
		if (root != null) {
			//如果root 只有一个节点，判断root 是不是要删的
			if (root.getNo() == no) {
				root = null;
			} else {
				root.deleteNode(no);
			}
		} else {
			System.out.println("为空");
		}
	}

}


//创建 HeroNode 节点
class HeroNode {
	private int no;
	private String name;
	private HeroNode left;
	private HeroNode right;

	public HeroNode(int no, String name) {
		this.no = no;
		this.name = name;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public HeroNode getLeft() {
		return left;
	}

	public void setLeft(HeroNode left) {
		this.left = left;
	}

	public HeroNode getRight() {
		return right;
	}

	public void setRight(HeroNode right) {
		this.right = right;
	}

	@Override
	public String toString() {
		return "HeroNode{" +
				"no=" + no +
				", name='" + name + '\'' +
				'}';
	}

	//前序遍历的方法
	public void preOrder() {
		//1.先输出父节点
		System.out.println(this);
		//2.递归向左子树前序遍历
		if (this.left != null) {
			this.left.preOrder();
		}
		//3.递归向右子树前序遍历
		if (this.right != null) {
			this.right.preOrder();
		}
	}

	//中序
	public void infixOrder() {
		//1.递归向左子树中序遍历
		if (this.left != null) {
			this.left.infixOrder();
		}
		//2.输出父节点
		System.out.println(this);
		//3.递归向右子树中序遍历
		if (this.right != null) {
			this.right.infixOrder();
		}
	}

	//后序
	public void postOrder() {
		//1.递归向左子树中序遍历
		if (this.left != null) {
			this.left.postOrder();
		}
		//2.递归向右子树中序遍历
		if (this.right != null) {
			this.right.postOrder();
		}
		//3.输出父节点
		System.out.println(this);
	}

	//前序遍历查找
	public HeroNode preOrderSearch(int no) {
		//比较当前节点是不是
		if (this.no == no) {
			return this;
		}

		HeroNode resultNode = null;
		if (this.left != null) {
			resultNode = this.left.preOrderSearch(no);
		}
		if (resultNode != null) {
			//如果成立在左子树上找到了
			return resultNode;
		}
		if (this.right != null) {
			resultNode = this.right.preOrderSearch(no);
		}

		return resultNode;
	}

	//中序遍历查找
	public HeroNode infixOrderSearch(int no) {

		HeroNode resultNode = null;
		if (this.left != null) {
			resultNode = this.left.infixOrderSearch(no);
		}
		if (resultNode != null) {
			//如果成立在左子树上找到了
			return resultNode;
		}

		//比较当前节点是不是
		if (this.no == no) {
			return this;
		}

		if (this.right != null) {
			resultNode = this.right.infixOrderSearch(no);
		}

		return resultNode;
	}

	//后序遍历查找
	public HeroNode postOrderSearch(int no) {
		HeroNode resultNode = null;
		if (this.left != null) {
			resultNode = this.left.postOrderSearch(no);
		}
		if (resultNode != null) {
			//如果成立在左子树上找到了
			return resultNode;
		}
		if (this.right != null) {
			resultNode = this.right.postOrderSearch(no);
		}
		if (resultNode != null) {
			//如果成立在右子树上找到了
			return resultNode;
		}
		//比较当前节点是不是
		if (this.no == no) {
			return this;
		}
		return resultNode;
	}


	//递归删除节点
	public void deleteNode(int no) {
		//先判断左子节点是否是要删除的
		if (this.left != null && this.left.no == no) {
			this.left = null;
			return;
		}
		//先判断右子节点是否是要删除的
		if (this.right != null && this.right.no == no) {
			this.right = null;
			return;
		}

		//左右都不是，向左子树递归
		if (this.left != null) {
			this.left.deleteNode(no);
		}

		//左右都不是，向右子树递归
		if (this.right != null) {
			this.right.deleteNode(no);
		}
	}

}
